0419. 棋盘上的战舰【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 一次扫描

1. 📝 题目描述

• leetcode

给你一个大小为 m x n 的矩阵 board 表示棋盘，其中，每个单元格可以是一艘战舰 'X' 或者是一个空位 '.'，返回在棋盘 board 上放置的 舰队 的数量。

舰队 只能水平或者垂直放置在 board 上。换句话说，舰队只能按 1 x k（1 行，k 列）或 k x 1（k 行，1 列）的形状放置，其中 k 可以是任意大小。两个舰队之间至少有一个水平或垂直的空格分隔 （即没有相邻的舰队）。

---

示例 1：

输入：board = [["X",".",".","X"],[".",".",".","X"],[".",".",".","X"]]
输出：2

示例 2：

输入：board = [["."]]
输出：0

---

提示：

• m == board.length
• n == board[i].length
• 1 <= m, n <= 200
• board[i][j] 是 '.' 或 'X'

进阶：你可以实现一次扫描算法，并只使用 O(1) 额外空间，并且不修改 board 的值来解决这个问题吗？

2. 🎯 s.1 - 一次扫描

c

int countBattleships(char** board, int boardSize, int* boardColSize) {
    int count = 0;
    for (int i = 0; i < boardSize; i++)
        for (int j = 0; j < boardColSize[0]; j++)
            if (board[i][j] == 'X' &&
                (i == 0 || board[i-1][j] != 'X') &&
                (j == 0 || board[i][j-1] != 'X'))
                count++;
    return count;
}

js

/**
 * @param {character[][]} board
 * @return {number}
 */
var countBattleships = function (board) {
  let count = 0
  for (let i = 0; i < board.length; i++) {
    for (let j = 0; j < board[0].length; j++) {
      if (
        board[i][j] === 'X' &&
        (i === 0 || board[i - 1][j] !== 'X') &&
        (j === 0 || board[i][j - 1] !== 'X')
      ) {
        count++
      }
    }
  }
  return count
}

py

class Solution:
    def countBattleships(self, board: List[List[str]]) -> int:
        count = 0
        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] == 'X' and (i == 0 or board[i-1][j] != 'X') and (j == 0 or board[i][j-1] != 'X'):
                    count += 1
        return count

• 时间复杂度：$O(m\times n)$
• 空间复杂度：$O(1)$

算法思路：

• 只统计战舰的“头部”：左方和上方都不是 X 的位置
• 不需要修改原矩阵，不需要额外空间